翻訳と辞書 Words near each other ・ Consinka Lake ・ Consip ・ Consistency ・ Consistency (database systems) ・ Consistency (disambiguation) ・ Consistency (knowledge bases) ・ Consistency (negotiation) ・ Consistency (statistics) ・ Consistency (suspension) ・ Consistency criterion ・ Consistency model ・ Consistency Theory ・ Consistent and inconsistent equations ・ Consistent estimator ・ Consistent hashing ・ Consistent heuristic ・ Consistent histories ・ Consistent life ethic ・ Consistent Network Device Naming ・ Consistent Overhead Byte Stuffing ・ Consistent pricing process ・ Consistori de Barcelona ・ Consistori del Gay Saber ・ Consistory ・ Consistory (Judaism) ・ Consistory (Protestantism) ・ Consistory court ・ Consociationalism ・ Consol ・ Consol (bond) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Consistent heuristic ： ウィキペディア英語版 Consistent heuristic In the study of path-finding problems in artificial intelligence, a consistent (or monotone) heuristic function is a function that estimates the distance of a given state to a goal state, and that is always at most equal to the estimated distance from any neighboring vertex plus the step cost of reaching that neighbor. Formally, for every node ''N'' and every successor ''P'' of ''N'' generated by any action ''a'', the estimated cost of reaching the goal from ''N'' is no greater than the step cost of getting to ''P'' plus the estimated cost of reaching the goal from ''P''. In other words: : $h(N)\; \backslash leq\; c(N,P)\; +\; h(P)$ and : $h(G)\; =\; 0.\backslash ,$ where : * ''h'' is the consistent heuristic function : * ''N'' is any node in the graph : * ''P'' is any descendant of ''N'' : * ''G'' is any goal node : * c(N,P) is the cost of reaching node P from N A consistent heuristic is also admissible, i.e. it never overestimates the cost of reaching the goal (the opposite however is not always true!). This is proved by induction on $m$, the length of the best path from node to goal. By assumption, $h(N\_m)\; \backslash leq\; h^$ *(N_m), where $h^$ *(n) denotes the cost of the shortest path from ''n'' to the goal. Therefore, :$h(N\_)\; \backslash leq\; c(N\_,\; N\_m)\; +\; h(N\_m)\; \backslash leq\; c(N\_,\; N\_m)\; +\; h^$ *(N_m) = h^ *(N_), making it admissible. ($N\_$ is any node whose best path to the goal, of length m+1, goes through some immediate child $N\_$ whose best path to the goal is of length m.) However, an admissible heuristic $h$, can be made into a consistent heuristic, $h\text{'}$, through the following adjustment: : $h\text{'}(P)\; \backslash gets\; \backslash max(h(P),\; h(N)\; -\; c(N,P))$ (Known as the pathmax equation.) ==Consequences of monotonicity== Consistent heuristics are called monotone because the estimated final cost of a partial solution, $f(N\_j)=g(N\_j)+h(N\_j)$ is monotonically non-decreasing along the best path to the goal, where $g(N\_j)=\backslash sum\_^j\; c(N\_,N\_i)$ is the cost of the best path from start node $N\_1$ to $N\_j$. It's necessary and sufficient for a heuristic to obey the triangle inequality in order to be consistent. In the A * search algorithm, using a consistent heuristic means that once a node is expanded, the cost by which it was reached is the lowest possible, under the same conditions that Dijkstra's algorithm requires in solving the shortest path problem (no negative cost cycles). In fact, if the search graph is given cost $c\text{'}(N,P)=c(N,P)+h(P)-h(N)$ for a consistent $h$, then A * is equivalent to best-first search on that graph using Dijkstra's algorithm.〔 In the unusual event that an admissible heuristic is not consistent, a node will need repeated expansion every time a new best (so-far) cost is achieved for it. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Consistent heuristic」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.